It would be desirable to provide a computer capability to quickly search for regions on the surface of the earth. Examples of regions are polygons, circles, and boxes. Regions may be associated with documents stored in a database. Therefore, it would be desirable to provide a user with the ability to query the database using a query region and a spatial predicate, such as defined in the Dimensionally Extended Nine-Intersection Model (DE-9IM). The spatial predicate is a space relation between the query region and regions in the database, such as equals, disjoint, touches, contains, intersects, inside and covered by.
An example query is to “find all regions that overlap with a circle of radius 100 km centered on San Francisco.” The database should then provide all documents that contain matching regions.
Existing region indexes are usually based on one of two techniques: R-trees and quadtrees/geohashes. In the R-tree approach, the minimum bounding rectangles (MBRs) of the stored regions are indexed using an R-tree data structure. At query time, the index is searched using the MBR of the query region. If the MBRs interact appropriately, the stored region is considered to be a match.
In the quadtree/geohash approach, the earth is divided into a grid, with the grid squares organized hierarchically into a tree. A leaf node in this tree tracks which stored regions intersect with the grid square. At query time, a node in the tree is only searched if the query region interacts with that grid square.
Either approach can yield false positives, so it is typical to see it combined with a secondary index or filter step that retrieves the region from storage and checks it against the query region. For regions such as polygons, this is done using computational geometry techniques. This geometry is the most expensive part of the query. The primary purpose of the index is to reduce the number of geometry calculations that must be performed.
Existing indexes generally operate independently of a coordinate system. That is, regions on a geographic coordinate system (i.e., on the earth) are indexed in the same way for a Euclidean coordinate system (i.e., a flat plane) using MBRs or a grid system. For a geographic coordinate system, the geometry calculations of the secondary filter must be performed using ellipsoid geometry, which are more expensive than the calculations for Euclidean geometry.
Accordingly, it would be desirable to provide a system that reduces the query time expense of ellipsoidal geometric calculations associated with a geospatial search.